Termination w.r.t. Q proof of /tmp/tmpekeQQg/cime1.trs

Termination w.r.t. Q of the following Term Rewriting System could be proven:

Q restricted rewrite system:
The TRS R consists of the following rules:

sortSu(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) → sortSu(cons(te(msubst(te(a), sortSu(t))), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) → sortSu(cons(te(a), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) → sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) → sortSu(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u)))))
sortSu(circ(sortSu(s), sortSu(id))) → sortSu(s)
sortSu(circ(sortSu(id), sortSu(s))) → sortSu(s)
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) → sortSu(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u)))
te(subst(te(a), sortSu(id))) → te(a)
te(msubst(te(a), sortSu(id))) → te(a)
te(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) → te(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t)))))

Q is empty.

↳ QTRS

  ↳ DependencyPairsProof

Q restricted rewrite system:
The TRS R consists of the following rules:

sortSu(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) → sortSu(cons(te(msubst(te(a), sortSu(t))), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) → sortSu(cons(te(a), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) → sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) → sortSu(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u)))))
sortSu(circ(sortSu(s), sortSu(id))) → sortSu(s)
sortSu(circ(sortSu(id), sortSu(s))) → sortSu(s)
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) → sortSu(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u)))
te(subst(te(a), sortSu(id))) → te(a)
te(msubst(te(a), sortSu(id))) → te(a)
te(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) → te(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t)))))

Q is empty.

Using Dependency Pairs [1,15] we result in the following initial DP problem:
Q DP problem:
The TRS P consists of the following rules:

SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) → SORTSU(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t)))))
SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) → SORTSU(circ(sortSu(s), sortSu(t)))
SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) → SORTSU(cons(te(a), sortSu(circ(sortSu(s), sortSu(t)))))
SORTSU(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) → SORTSU(circ(sortSu(s), sortSu(t)))
SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) → SORTSU(circ(sortSu(s), sortSu(t)))
SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) → SORTSU(circ(sortSu(s), sortSu(t)))
SORTSU(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) → SORTSU(circ(sortSu(t), sortSu(u)))
SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) → SORTSU(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t)))))
SORTSU(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) → SORTSU(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u)))))
SORTSU(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) → SORTSU(cons(te(msubst(te(a), sortSu(t))), sortSu(circ(sortSu(s), sortSu(t)))))
TE(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) → SORTSU(circ(sortSu(s), sortSu(t)))
TE(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) → TE(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t)))))
SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) → SORTSU(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u)))
SORTSU(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) → TE(msubst(te(a), sortSu(t)))

The TRS R consists of the following rules:

sortSu(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) → sortSu(cons(te(msubst(te(a), sortSu(t))), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) → sortSu(cons(te(a), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) → sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) → sortSu(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u)))))
sortSu(circ(sortSu(s), sortSu(id))) → sortSu(s)
sortSu(circ(sortSu(id), sortSu(s))) → sortSu(s)
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) → sortSu(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u)))
te(subst(te(a), sortSu(id))) → te(a)
te(msubst(te(a), sortSu(id))) → te(a)
te(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) → te(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t)))))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ DependencyGraphProof

Q DP problem:
The TRS P consists of the following rules:

SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) → SORTSU(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t)))))
SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) → SORTSU(circ(sortSu(s), sortSu(t)))
SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) → SORTSU(cons(te(a), sortSu(circ(sortSu(s), sortSu(t)))))
SORTSU(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) → SORTSU(circ(sortSu(s), sortSu(t)))
SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) → SORTSU(circ(sortSu(s), sortSu(t)))
SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) → SORTSU(circ(sortSu(s), sortSu(t)))
SORTSU(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) → SORTSU(circ(sortSu(t), sortSu(u)))
SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) → SORTSU(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t)))))
SORTSU(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) → SORTSU(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u)))))
SORTSU(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) → SORTSU(cons(te(msubst(te(a), sortSu(t))), sortSu(circ(sortSu(s), sortSu(t)))))
TE(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) → SORTSU(circ(sortSu(s), sortSu(t)))
TE(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) → TE(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t)))))
SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) → SORTSU(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u)))
SORTSU(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) → TE(msubst(te(a), sortSu(t)))

The TRS R consists of the following rules:

sortSu(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) → sortSu(cons(te(msubst(te(a), sortSu(t))), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) → sortSu(cons(te(a), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) → sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) → sortSu(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u)))))
sortSu(circ(sortSu(s), sortSu(id))) → sortSu(s)
sortSu(circ(sortSu(id), sortSu(s))) → sortSu(s)
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) → sortSu(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u)))
te(subst(te(a), sortSu(id))) → te(a)
te(msubst(te(a), sortSu(id))) → te(a)
te(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) → te(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t)))))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [15,17,22] contains 1 SCC with 4 less nodes.

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ DependencyGraphProof

        ↳ QDP

          ↳ QDPOrderProof

Q DP problem:
The TRS P consists of the following rules:

SORTSU(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) → SORTSU(circ(sortSu(t), sortSu(u)))
SORTSU(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) → SORTSU(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u)))))
SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) → SORTSU(circ(sortSu(s), sortSu(t)))
SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) → SORTSU(circ(sortSu(s), sortSu(t)))
SORTSU(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) → SORTSU(circ(sortSu(s), sortSu(t)))
SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) → SORTSU(circ(sortSu(s), sortSu(t)))
TE(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) → SORTSU(circ(sortSu(s), sortSu(t)))
TE(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) → TE(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t)))))
SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) → SORTSU(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u)))
SORTSU(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) → TE(msubst(te(a), sortSu(t)))

The TRS R consists of the following rules:

sortSu(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) → sortSu(cons(te(msubst(te(a), sortSu(t))), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) → sortSu(cons(te(a), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) → sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) → sortSu(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u)))))
sortSu(circ(sortSu(s), sortSu(id))) → sortSu(s)
sortSu(circ(sortSu(id), sortSu(s))) → sortSu(s)
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) → sortSu(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u)))
te(subst(te(a), sortSu(id))) → te(a)
te(msubst(te(a), sortSu(id))) → te(a)
te(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) → te(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t)))))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [15].

The following pairs can be oriented strictly and are deleted.

SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) → SORTSU(circ(sortSu(s), sortSu(t)))
SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) → SORTSU(circ(sortSu(s), sortSu(t)))
SORTSU(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) → SORTSU(circ(sortSu(s), sortSu(t)))
SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) → SORTSU(circ(sortSu(s), sortSu(t)))
TE(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) → SORTSU(circ(sortSu(s), sortSu(t)))
SORTSU(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) → SORTSU(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u)))

The remaining pairs can at least be oriented weakly.

SORTSU(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) → SORTSU(circ(sortSu(t), sortSu(u)))
SORTSU(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) → SORTSU(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u)))))
TE(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) → TE(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t)))))
SORTSU(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) → TE(msubst(te(a), sortSu(t)))

Used ordering: Polynomial interpretation with max and min functions [25]:

POL(SORTSU(x₁)) = x₁
POL(TE(x₁)) = 1 + x₁
POL(circ(x₁, x₂)) = x₁ + x₂
POL(cons(x₁, x₂)) = 1 + max(x₁, x₂)
POL(id) = 0
POL(lift) = 0
POL(msubst(x₁, x₂)) = x₁ + x₂
POL(sop(x₁)) = 0
POL(sortSu(x₁)) = x₁
POL(subst(x₁, x₂)) = x₁
POL(te(x₁)) = x₁

The following usable rules [17] were oriented:

sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) → sortSu(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u)))
sortSu(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) → sortSu(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u)))))
sortSu(circ(sortSu(s), sortSu(id))) → sortSu(s)
sortSu(circ(sortSu(id), sortSu(s))) → sortSu(s)
te(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) → te(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t)))))
te(msubst(te(a), sortSu(id))) → te(a)
te(subst(te(a), sortSu(id))) → te(a)
sortSu(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) → sortSu(cons(te(msubst(te(a), sortSu(t))), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) → sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) → sortSu(cons(te(a), sortSu(circ(sortSu(s), sortSu(t)))))

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ DependencyGraphProof

        ↳ QDP

          ↳ QDPOrderProof

            ↳ QDP

              ↳ DependencyGraphProof

Q DP problem:
The TRS P consists of the following rules:

SORTSU(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) → SORTSU(circ(sortSu(t), sortSu(u)))
SORTSU(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) → SORTSU(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u)))))
TE(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) → TE(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t)))))
SORTSU(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) → TE(msubst(te(a), sortSu(t)))

The TRS R consists of the following rules:

sortSu(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) → sortSu(cons(te(msubst(te(a), sortSu(t))), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) → sortSu(cons(te(a), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) → sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) → sortSu(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u)))))
sortSu(circ(sortSu(s), sortSu(id))) → sortSu(s)
sortSu(circ(sortSu(id), sortSu(s))) → sortSu(s)
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) → sortSu(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u)))
te(subst(te(a), sortSu(id))) → te(a)
te(msubst(te(a), sortSu(id))) → te(a)
te(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) → te(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t)))))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [15,17,22] contains 2 SCCs with 1 less node.

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ DependencyGraphProof

        ↳ QDP

          ↳ QDPOrderProof

            ↳ QDP

              ↳ DependencyGraphProof

                ↳ AND

                  ↳ QDP

                    ↳ QDPOrderProof

                  ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

TE(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) → TE(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t)))))

The TRS R consists of the following rules:

sortSu(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) → sortSu(cons(te(msubst(te(a), sortSu(t))), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) → sortSu(cons(te(a), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) → sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) → sortSu(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u)))))
sortSu(circ(sortSu(s), sortSu(id))) → sortSu(s)
sortSu(circ(sortSu(id), sortSu(s))) → sortSu(s)
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) → sortSu(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u)))
te(subst(te(a), sortSu(id))) → te(a)
te(msubst(te(a), sortSu(id))) → te(a)
te(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) → te(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t)))))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [15].

The following pairs can be oriented strictly and are deleted.

TE(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) → TE(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t)))))

The remaining pairs can at least be oriented weakly.
none
Used ordering: Polynomial interpretation [25]:

POL(TE(x₁)) = x₁
POL(circ(x₁, x₂)) = 0
POL(cons(x₁, x₂)) = 0
POL(id) = 0
POL(lift) = 0
POL(msubst(x₁, x₂)) = 1 + x₁
POL(sop(x₁)) = 0
POL(sortSu(x₁)) = 0
POL(subst(x₁, x₂)) = x₁
POL(te(x₁)) = 1 + x₁

The following usable rules [17] were oriented:

sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) → sortSu(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u)))
sortSu(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) → sortSu(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u)))))
sortSu(circ(sortSu(s), sortSu(id))) → sortSu(s)
sortSu(circ(sortSu(id), sortSu(s))) → sortSu(s)
te(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) → te(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t)))))
te(msubst(te(a), sortSu(id))) → te(a)
te(subst(te(a), sortSu(id))) → te(a)
sortSu(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) → sortSu(cons(te(msubst(te(a), sortSu(t))), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) → sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) → sortSu(cons(te(a), sortSu(circ(sortSu(s), sortSu(t)))))

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ DependencyGraphProof

        ↳ QDP

          ↳ QDPOrderProof

            ↳ QDP

              ↳ DependencyGraphProof

                ↳ AND

                  ↳ QDP

                    ↳ QDPOrderProof

                      ↳ QDP

                        ↳ PisEmptyProof

                  ↳ QDP

Q DP problem:
P is empty.
The TRS R consists of the following rules:

sortSu(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) → sortSu(cons(te(msubst(te(a), sortSu(t))), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) → sortSu(cons(te(a), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) → sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) → sortSu(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u)))))
sortSu(circ(sortSu(s), sortSu(id))) → sortSu(s)
sortSu(circ(sortSu(id), sortSu(s))) → sortSu(s)
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) → sortSu(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u)))
te(subst(te(a), sortSu(id))) → te(a)
te(msubst(te(a), sortSu(id))) → te(a)
te(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) → te(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t)))))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The TRS P is empty. Hence, there is no (P,Q,R) chain.

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ DependencyGraphProof

        ↳ QDP

          ↳ QDPOrderProof

            ↳ QDP

              ↳ DependencyGraphProof

                ↳ AND

                  ↳ QDP

                  ↳ QDP

                    ↳ QDPOrderProof

Q DP problem:
The TRS P consists of the following rules:

SORTSU(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) → SORTSU(circ(sortSu(t), sortSu(u)))
SORTSU(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) → SORTSU(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u)))))

The TRS R consists of the following rules:

sortSu(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) → sortSu(cons(te(msubst(te(a), sortSu(t))), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) → sortSu(cons(te(a), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) → sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) → sortSu(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u)))))
sortSu(circ(sortSu(s), sortSu(id))) → sortSu(s)
sortSu(circ(sortSu(id), sortSu(s))) → sortSu(s)
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) → sortSu(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u)))
te(subst(te(a), sortSu(id))) → te(a)
te(msubst(te(a), sortSu(id))) → te(a)
te(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) → te(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t)))))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [15].

The following pairs can be oriented strictly and are deleted.

SORTSU(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) → SORTSU(circ(sortSu(t), sortSu(u)))

The remaining pairs can at least be oriented weakly.

SORTSU(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) → SORTSU(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u)))))

Used ordering: Polynomial interpretation [25]:

POL(SORTSU(x₁)) = x₁
POL(circ(x₁, x₂)) = 1 + x₁ + x₂
POL(cons(x₁, x₂)) = 1 + x₁ + x₂
POL(id) = 0
POL(lift) = 0
POL(msubst(x₁, x₂)) = 0
POL(sop(x₁)) = 1
POL(sortSu(x₁)) = x₁
POL(subst(x₁, x₂)) = 0
POL(te(x₁)) = 1

The following usable rules [17] were oriented:

sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) → sortSu(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u)))
sortSu(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) → sortSu(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u)))))
sortSu(circ(sortSu(s), sortSu(id))) → sortSu(s)
sortSu(circ(sortSu(id), sortSu(s))) → sortSu(s)
te(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) → te(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t)))))
te(msubst(te(a), sortSu(id))) → te(a)
te(subst(te(a), sortSu(id))) → te(a)
sortSu(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) → sortSu(cons(te(msubst(te(a), sortSu(t))), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) → sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) → sortSu(cons(te(a), sortSu(circ(sortSu(s), sortSu(t)))))

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ DependencyGraphProof

        ↳ QDP

          ↳ QDPOrderProof

            ↳ QDP

              ↳ DependencyGraphProof

                ↳ AND

                  ↳ QDP

                  ↳ QDP

                    ↳ QDPOrderProof

                      ↳ QDP

                        ↳ QDPOrderProof

Q DP problem:
The TRS P consists of the following rules:

SORTSU(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) → SORTSU(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u)))))

The TRS R consists of the following rules:

sortSu(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) → sortSu(cons(te(msubst(te(a), sortSu(t))), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) → sortSu(cons(te(a), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) → sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) → sortSu(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u)))))
sortSu(circ(sortSu(s), sortSu(id))) → sortSu(s)
sortSu(circ(sortSu(id), sortSu(s))) → sortSu(s)
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) → sortSu(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u)))
te(subst(te(a), sortSu(id))) → te(a)
te(msubst(te(a), sortSu(id))) → te(a)
te(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) → te(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t)))))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [15].

The following pairs can be oriented strictly and are deleted.

SORTSU(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) → SORTSU(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u)))))

The remaining pairs can at least be oriented weakly.
none
Used ordering: Matrix interpretation [3]:
Non-tuple symbols:

M( cons(x₁, x₂) ) =

/	0	\
\	0	/

/	0	0	\
\	0	0	/

x₁

/	0	0	\
\	0	0	/

x₂

M( sop(x₁) ) =

/	0	\
\	0	/

/	0	0	\
\	0	0	/

x₁

M( subst(x₁, x₂) ) =

/	0	\
\	0	/

/	0	0	\
\	0	0	/

x₁

/	0	0	\
\	0	0	/

x₂

M( te(x₁) ) =

/	0	\
\	0	/

/	0	0	\
\	0	0	/

x₁

M( circ(x₁, x₂) ) =

/	1	\
\	0	/

/	0	0	\
\	1	0	/

x₁

/	1	0	\
\	0	0	/

x₂

M( lift ) =

/	0	\
\	0	/

M( id ) =

/	0	\
\	0	/

M( sortSu(x₁) ) =

/	0	\
\	0	/

/	1	1	\
\	0	0	/

x₁

M( msubst(x₁, x₂) ) =

/	0	\
\	0	/

/	0	0	\
\	0	0	/

x₁

/	0	0	\
\	0	0	/

x₂

Tuple symbols:

M( SORTSU(x₁) ) =

[

]

x₁

Matrix type:
We used a basic matrix type which is not further parametrizeable.

As matrix orders are CE-compatible, we used usable rules w.r.t. argument filtering in the order.
The following usable rules [17] were oriented:

sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) → sortSu(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u)))
sortSu(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) → sortSu(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u)))))
sortSu(circ(sortSu(s), sortSu(id))) → sortSu(s)
sortSu(circ(sortSu(id), sortSu(s))) → sortSu(s)
te(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) → te(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t)))))
te(msubst(te(a), sortSu(id))) → te(a)
te(subst(te(a), sortSu(id))) → te(a)
sortSu(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) → sortSu(cons(te(msubst(te(a), sortSu(t))), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) → sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) → sortSu(cons(te(a), sortSu(circ(sortSu(s), sortSu(t)))))

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ DependencyGraphProof

        ↳ QDP

          ↳ QDPOrderProof

            ↳ QDP

              ↳ DependencyGraphProof

                ↳ AND

                  ↳ QDP

                  ↳ QDP

                    ↳ QDPOrderProof

                      ↳ QDP

                        ↳ QDPOrderProof

                          ↳ QDP

                            ↳ PisEmptyProof

Q DP problem:
P is empty.
The TRS R consists of the following rules:

sortSu(circ(sortSu(cons(te(a), sortSu(s))), sortSu(t))) → sortSu(cons(te(msubst(te(a), sortSu(t))), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(te(a), sortSu(t))))) → sortSu(cons(te(a), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(cons(sop(lift), sortSu(t))))) → sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t)))))
sortSu(circ(sortSu(circ(sortSu(s), sortSu(t))), sortSu(u))) → sortSu(circ(sortSu(s), sortSu(circ(sortSu(t), sortSu(u)))))
sortSu(circ(sortSu(s), sortSu(id))) → sortSu(s)
sortSu(circ(sortSu(id), sortSu(s))) → sortSu(s)
sortSu(circ(sortSu(cons(sop(lift), sortSu(s))), sortSu(circ(sortSu(cons(sop(lift), sortSu(t))), sortSu(u))))) → sortSu(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(s), sortSu(t))))), sortSu(u)))
te(subst(te(a), sortSu(id))) → te(a)
te(msubst(te(a), sortSu(id))) → te(a)
te(msubst(te(msubst(te(a), sortSu(s))), sortSu(t))) → te(msubst(te(a), sortSu(circ(sortSu(s), sortSu(t)))))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The TRS P is empty. Hence, there is no (P,Q,R) chain.